package leet_code;

import java.util.*;

/**
 * 普通数组
 */
public class A_5_Array {

    /**
     * 53. 最大子数组和
     * https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-100-liked
     *
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组 是数组中的一个连续部分。
     *
     * 示例 1：
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     *
     * 示例 2：
     * 输入：nums = [1]
     * 输出：1
     *
     * 示例 3：
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     *
     *
     * 提示：
     * 1 <= nums.length <= 10^5
     * -10^4 <= nums[i] <= 10^4
     *
     *
     * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        //记录前缀和

        int max = nums[0];
        for (int left = 0; left < nums.length; left++) {
            //从左往右遍历，当和小于1并且
            int sum = 0;
            for (int right = left; right < nums.length; right++) {
                //如果和小于零 left左移至right加一位置
                sum = sum + nums[right];
                max = Math.max(max, sum);
                if (sum <= 0) {
                    left = right;
                    break;
                }
            }
            if (sum > 0) {
                break;
            }
        }
        return max;
    }


    /**
     * 56. 合并区间
     * https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     *
     * 示例 1：
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * 示例 2：
     * 输入：intervals = [[1,4],[4,5]]
     * 输出：[[1,5]]
     * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
     *
     *
     * 提示：
     * 1 <= intervals.length <= 10^4
     * intervals[i].length == 2
     * 0 <= starti <= endi <= 10^4
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        //intervals 排序
//        for (int i = 0; i < intervals.length; i++) {
//            for (int j = i + 1; j < intervals.length; j++) {
//                if (intervals[j - 1][0] > intervals[j][0]) {
//                    int[] temp = intervals[j - 1];
//                    intervals[j-1] = intervals[j];
//                    intervals[j] = temp;
//                }
//            }
//        }
//
//        //遍历数组
//        List<List<Integer>> arrs = new ArrayList<>();
//        for (int left = 0; left < intervals.length; left++) {
//            List<Integer> arr = new ArrayList<>();
//            arr.add(intervals[left][0]);
//            int compareNum = intervals[left][1];
//            //特殊情况
//            if (left == intervals.length - 1) {
//                arr.add(compareNum);
//            }
//            for (int right = left + 1; right < intervals.length; right++) {
//                if (compareNum < intervals[right][0]) {
//                    arr.add(compareNum);
//                    left = right - 1;
//                    break;
//                } else if (compareNum > intervals[right][1]){
//                    left = right;
//                    continue;
//                } else {
//                    arr.add(intervals[right][1]);
//                    left = right;
//                    break;
//                }
//            }
//            if (arr.size() < 2) {
//                arr.add(compareNum);
//            }
//            arrs.add(arr);
//        }
//
//        //构造返回值
//        int[][] res = new int[arrs.size()][2];
//        for (int i = 0; i < res.length; i++) {
//            for (int i1 = 0; i1 < res[i].length; i1++) {
//                res[i][i1] = arrs.get(i).get(i1);
//            }
//        }
//        return res;


        if (intervals.length == 0) {
            return new int[0][2];
        }
        //排序待合并的区间
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        List<int[]> merged = new ArrayList<>();

        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            //如果合并后的最右侧数据小于，当前最左侧数据则说明断层，将后续的区间加入
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                //如果在区间内，则比较右侧数据，取较大者
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    /**
     * 189. 轮转数组
     * https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&envId=top-100-liked
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     *
     * 示例 1:
     * 输入: nums = [1,2,3,4,5,6,7], k = 3
     * 输出: [5,6,7,1,2,3,4]
     *
     * 解释:
     * 向右轮转 1 步: [7,1,2,3,4,5,6]
     * 向右轮转 2 步: [6,7,1,2,3,4,5]
     * 向右轮转 3 步: [5,6,7,1,2,3,4]
     *
     * 示例 2:
     * 输入：nums = [-1,-100,3,99], k = 2
     * 输出：[3,99,-1,-100]
     *
     * 解释:
     * 向右轮转 1 步: [99,-1,-100,3]
     * 向右轮转 2 步: [3,99,-1,-100]
     *
     *
     * 提示：
     * 1 <= nums.length <= 10^5
     * -2^31 <= nums[i] <= 2^31 - 1
     * 0 <= k <= 10^5
     *
     * 进阶：
     * 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
     * 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
//        方法一：辅助数组拷贝 空间复杂度O(n)、时间复杂度O(n)
//        k = k % nums.length;
//        if (k == 0) {
//            return;
//        }
//        int[] res = new int[nums.length];
//        int count = 0;
//        //将原数组后半部放到新数组的前方
//        for (int i = nums.length - k; i < nums.length; i++) {
//            res[count] = nums[i];
//            count++;
//        }
//        //将原数组的前半部分追加到新数组的后方
//        for (int i = 0; i < nums.length - k; i++) {
//            res[count] = nums[i];
//            count++;
//        }
//        //对原数组进行赋值
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = res[i];
//        }

//        方法二：原地移动，移动k轮法
        k = k % nums.length;
        if (k == 0) {
            return;
        }
        for (int i = 0; i < k; i++) {
            int end = nums[nums.length - 1];
            //移动每个数，记录末尾
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = end;
        }

        //方法三：反转法
        /**
         * nums = "----->-->"; k =3
         * result = "-->----->";
         *
         * reverse "----->-->" we can get "<--<-----"
         * reverse "<--" we can get "--><-----"
         * reverse "<-----" we can get "-->----->"
         * this visualization help me figure it out :)
         */
    }

    /**
     * 238. 除自身以外数组的乘积
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     *
     * 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     * 示例 1:
     * 输入: nums = [1,2,3,4]
     * 输出: [24,12,8,6]
     *
     * 示例 2:
     * 输入: nums = [-1,1,0,-3,3]
     * 输出: [0,0,9,0,0]
     *
     * 提示：
     * 2 <= nums.length <= 10^5
     * -30 <= nums[i] <= 30
     * 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
     *
     * 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        //记录从前往后&从后往前的n数相乘和
        //从前往后
        Map<Integer, Integer> p2q = new HashMap<>(nums.length);
        //从后往前
        Map<Integer, Integer> q2p = new HashMap<>(nums.length);
        //初始化前map
        int mul = nums[0];
        p2q.put(0, mul);
        for (int i = 1; i < nums.length; i++) {
            mul = nums[i] * mul;
            p2q.put(i, mul);
        }
        //初始化后map
        mul = nums[nums.length - 1];
        q2p.put(nums.length - 1, mul);
        for (int i = nums.length - 2; i >= 0; i--) {
            mul = nums[i] * mul;
            q2p.put(i, mul);
        }

        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i - 1 < 0 && i + 1 >= nums.length) {
                break;
            }
            //当i - 1 小于0时，左边数组不存在，乘积和为i+1的 q2p
            if (i - 1 < 0) {
                res[i] = q2p.get(i + 1);
                continue;
            }
            if (i + 1 >= nums.length) {
                res[i] = p2q.get(i - 1);
            } else {
                res[i] = p2q.get(i - 1) * q2p.get(i + 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        A_5_Array array = new A_5_Array();
//        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
//        int[] arr = {1};
//        int[] arr = {5,4,-1,7,8};
//        int[] arr = {-2, -1};
//        System.out.println(array.maxSubArray(arr));
//        ------------------------------------
//        int[][] arrs = {{1,3},{2,6},{8,10},{15,18}};
//        int[][] arrs = {{1,4},{4,5}};
//        int[][] arrs = {{1,4},{0,4}};
//        int[][] arrs = {{1,4},{2,3}};
//        int[][] merge = array.merge(arrs);
//        for (int[] ints : merge) {
//            for (int anInt : ints) {
//                System.out.print(anInt + " ");
//            }
//            System.out.println();
//        }
//        --------------------------------
//        int[] arr = {1,2,3,4,5,6,7};
//        int k = 3;
//        int[] arr = {-1,-100,3,99};
//        int k = 2;
//        array.rotate(arr,k);
//        for (int i : arr) {
//            System.out.print(i + " ");
//        }
//        -----------------------------------
//        int[] arr = {1,2,3,4};
        int[] arr = {-1,1,0,-3,3};
//        int[] arr = {-1,1};
        int[] ints = array.productExceptSelf(arr);
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }
}
